Recursive Algorithm Design Patterns

Recursion Templates

Recursion is one of the most powerful tools in algorithm design.
Many algorithms follow common recursive templates, which can be recognised and reused.

1. Divide and Conquer (Splitting in Half)

• Idea: Split input into two halves, recurse on each, then combine.
• Examples: Binary search, merge sort, matrix multiplication.

function DivideAndConquer(A, lo, hi):
    if lo = hi: return BASE               # Modification Point 1
    mid = (lo+hi)//2
    left  = DivideAndConquer(A, lo, mid)
    right = DivideAndConquer(A, mid+1, hi)
    return COMBINE(left, right)           # Modification Point 2

Modification Points

• Base: return element, check condition, or stop recursion.
• Combine: merge results, take max/min, add counts, etc.

---

2. Generate Contiguous Subarrays

• Idea: Choose a starting index and extend step by step.
• Examples: Enumerating intervals, brute-force maximum subarray.

function subarrays(A):
    for i from 1 to length(A):
        extend_from(A, i, i)

function extend_from(A, i, j):
    if j > length(A): return
    PROCESS(A[i..j])                  # Modification Point
    extend_from(A, i, j+1)

Modification Point

• Print or collect subarray.
• Check sum/product against a target.
• Track best/worst subarray by an objective.

---

3. Generate All Subsets (Power Set)

• Idea: At each index, choose to include or exclude.
• Examples: Subset-sum, exhaustive knapsack, combinatorial search.

function subsets(A, i, current):
    if i = length(A):
        PROCESS(current)              # Modification Point
        return
    subsets(A, i+1, current)              # exclude
    subsets(A, i+1, current + [A[i]])     # include

Modification Point

• Output every subset.
• Restrict to subsets of size \(k\).
• Check sum/weight against a target.
• Evaluate subset for optimization.

---

4. Depth-First Search (DFS Traversal)

• Idea: Visit a node, then recursively visit neighbours.
• Examples: Graph traversal, connectivity, topological sorting.

function DFS(u):
    mark u visited
    PREPROCESS(u)                      # Modification Point 1
    for v in neighbours(u):
        if not visited(v):
            DFS(v)
    POSTPROCESS(u)                     # Modification Point 2

Modification Points

• record discovery order
• compute finishing times
• detect cycles

---

5. Backtracking (Systematic Search with Undo)

• Idea: Explore all possible choices; after exploring one path, undo the choice and try another.
• Examples: N-Queens, Sudoku solving, Hamiltonian paths, constraint satisfaction problems.

function Backtrack(state):
    if IS_SOLUTION(state):             # Modification Point 1
        PROCESS(state)
        return
    for choice in OPTIONS(state):
        if IS_VALID(choice, state):    # Modification Point 2
            MAKE(choice, state)        # apply choice
            Backtrack(state)           # recurse
            UNMAKE(choice, state)      # undo choice (backtrack)

Modification Points

• Is_Solution: Define when a complete/valid solution has been reached.
• Is_Valid: Prune invalid partial solutions early (pruning = efficiency).
• Process: Collect or count solutions, update a best-so-far.
• Make/Unmake: Modify the state (place/remove queen, assign/unassign value, etc.).

---

graph TD
    L((L))
    O_left((O))
    I((I))
    G((G))
    O_right((O))
    K1((K))
    P((P))
    K2((K))
    F((F))
    E1((E))
    E2((E))
    T((T))

    L --> O_left
    L --> I

    O_left --> G
    O_left --> O_right

    O_right --> K1
    O_right --> P

    I --> K2
    I --> F

    K2 --> E1
    F --> E2
    F --> T